Hierarchically-organized data, such as file system data and XML data, etc., is used in various environments, including in relational database systems and operating systems. For ease of illustration, reference is made herein to a database managing system with database structures. However, a managing system may be a database managing system or an operating system management system, etc.
Traditional relational database systems generally excel at handling structured content that maps to rows and columns, and may be extended to manage hierarchically-organized data. For example, the Oracle XML DB is a component of Oracle Database that is optimized for handling hierarchical data. The Oracle XML DB is described in more detail in the Oracle XML DB Developer's Guide, 10g Release 2 (10.2) Part Number B14259-02, Chapter 1, accessed on Jul. 31, 2009 at “docs/cd/B19306—01/appdev.102/b14259/xdb01int.htm#ADXDB0100” on the server “download.oracle.com”, the contents of which are incorporated by reference in their entirety for all purposes as if fully set forth herein.
Resources, such as files, folders, and xml nodes, etc., may be organized into hierarchical sets referred to herein as “repositories”. An example hierarchical repository 100 is illustrated in FIG. 1. Repository 100 includes a root container resource 102, and other resources 104-114. A container resource is a resource that is configured to include references to one or more other resources, such as a folder. In repository 100, resources 102, 104, 106, and 110 are container resources.
A database system may store information for resources in a resource table, which generally includes, for each resource, (a) a resource identifier, (b) content of the resource, (c) attributes of the resource, and (d) references to each child resource of the resource, etc. The database system may access information for a particular resource in a resource table based on the resource identifier for the particular resource, which may be a row identifier, or a logical identifier, etc. Such access may be through an index on the resource table, such as the hierarchical index of Oracle XML DB, described in the Oracle XML DB Developer's Guide, 10g Release 2, Part Number B14259-02, Chapter 20, accessed on Aug. 25, 2009, at “docs/cd/B19306—01/appdev.102/b14259/xdb16fol.htm#g1050290” on the server “download.oracle.com”, the contents of which are incorporated by reference in their entirety for all purposes as if fully set forth herein.
In a hierarchically-organized set of resources, such as repository 100, each particular resource is uniquely identified by a path expression, which generally includes (a) a list of ancestor container resources of the particular resource, and (b) the name of the particular resource. The resources listed in a path expression are separated by a special character, typically ‘/’ or ‘\’. A segment of a path expression is the name of one of the resources included in the path expression and delineated by special characters. For example, resource 108 has, as ancestor container resources, resources 102, 104, and 106. Therefore, a path expression that uniquely identifies resource 108, which includes the name of resource 108 and the names of the ancestor resources of resource 108, may be as follows: “\A\B\C”, where the initial ‘\’ represents root container resource 102, “A” represents resource 104, “B” represents resource 106, and “C” represents resource 108.
As referred to herein, the “target resource” of a particular path expression is the resource that is identified by the path expression. For example, resource 108 is the target resource of the path expression “\A\B\C” in repository 100. Resolving a path expression results in identifying information for the target resource of the path expression, such as a resource identifier, contents of a resource, attributes of a resource, etc.
To resolve a particular path expression, a managing system generally maps each segment of the particular path expression to a corresponding resource in a data structure in long-term storage that represents the resources of a repository, e.g., a resource database table. By mapping a first segment of a particular path expression to a resource in the data structure, the database system may search the list of child resources for the first segment resource found in the data structure for a mapping for the subsequent segment in the particular path expression. Thus, a managing system generally performs a segment by segment lookup to resolve a path expression to the path expression's target resource. Because resource tables in a database system are generally stored in long-term memory, mapping each segment of a path expression to a resource incurs a disk access for every segment.
A hierarchical repository may include a large number of resources, and may have a deep hierarchy. As such, it is common to resolve path expressions containing several container resource names. In fact, in many access mechanisms such as HTTP and WebDAV, the same path expression fragment (a path expression ending in a container resource) may be involved in multiple requests over the same or different connections. Thus, traditional path resolution results in significant overhead, especially when accessing small or medium-sized resources.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.